package 剑指Offer.简单;

/**
 * 统计一个数字在排序数组中出现的次数。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2022/8/27 10:29
 */
public class _53在排序数组中查找数字I {

    /**
     * 普通遍历
     */
    public int search(int[] nums, int target) {
        int count = 0;
        for (int n : nums) {
            if (target == n) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] a = {5, 6, 8, 8, 10};
        searchV2(a, 8);
        System.out.println();
    }

    /**
     * 使用二分法
     *  找到大于等于target最后出现的位置 right
     *  找到大于等于target-1最后出现的位置 left
     *  结果等于 right - left
     * @param nums
     * @param target
     * @return
     */
    public static int searchV2(int[] nums, int target) {
        return helperV2(nums, target) - helperV2(nums, target - 1);
    }


    static int helperV2(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int m = (left + right) / 2;
            // 如果中间数小于等于目标数 则不断后移
            if (nums[m] <= target) {
                left = m + 1;
            } else {
                right = m - 1;
            }
        }
        return left;
    }


    /**
     * 找到小于等于target的最右的坐标
     */
    static int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] <= tar)
                i = m + 1;
            else
                j = m - 1;
        }
        return i;
    }


}
